package lc2;

import org.junit.Test;

import util.TreeNode;
import util.TreeUtils;

/**
 * mirros遍历，转化搜索二叉树为有序双向链表
 */
public class Ex426 {

    class Solution {
        public TreeNode parseBST2OrderedList(TreeNode root) {
            TreeNode first = null;
            TreeNode last = null, cur = root;
            while (cur != null) {
                if (cur.left != null) {
                    TreeNode mostRight = cur.left;
                    while (mostRight.right != null && mostRight.right != cur) {
                        mostRight = mostRight.right;
                    }
                    if (mostRight.right != cur) {
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                    } else {
                        mostRight.right = null;
                    }
                }
                if (first == null) {
                    first = cur;
                }
                if (last != null) {
                    last.right = cur;
                    cur.left = last;
                }
                last = cur;
                cur = cur.right;
            }
            first.left = last;
            last.right = first;
            return first;
        }

    }

    @Test
    public void test() {
        Solution s = new Solution();
        Integer[] is = {4,2,5,1,3, null, null};
        TreeNode root = TreeUtils.createTree(is);
        TreeUtils.printBinaryTreeVisualization(root);
        TreeNode head = s.parseBST2OrderedList(root);
        TreeNode cur = head.right;
        System.out.println(head.val);
        while (cur != head) {
            System.out.println(cur.val);
            cur = cur.right;
        }
    }
    
}
